The present invention relates to a linear interpolating method for signals in a memory in which first signals are converted into second signals by addressing in at least a four-dimensional fashion, for use in a color picture processing machine such as a digital color scanner, a color facsimile, a color T.V. monitor, and other signal processing machines by converting coordinates of signals including at least four variables. The present invention can be effectively utilized when color separation signals of subtractive primary colors such as cyan C, magenta M, yellow Y and black K for printing inks are converted into color separation signals of additive primary colors such as red R, green G and blue B for reproducing a color image on a color cathode ray tube monitor or a color film.
Usually, in multicolor printing, the primary color inks for cyan C, magenta M, yellow Y and black K, which is used for improving the contrast of the dark part, are used. However, since the spectral characteristics of these color inks are usually different or shifted from those of the ideal subtractive primary colors, color separation picture signals of subtractive primary colors, C, M and Y can not be simply converted into color separation picture signals of additive primary colors R, G and B. That is, when an original picture is reproduced according to the simply converted picture signals, the desired colors can not be obtained and the obtained colors differ from those of the printed matter.
In addition to such differences of the spectral characteristics of the inks from the ideal primary color inks, a problem occurs when the picture is printed by overlapping the different color inks. That is, when the different color inks are printed, the density of the printed matter which is printed by the different color inks is lower than that of the sum of the densities of the different color inks, which is the so-called "addition law failure".
A method for carrying out the conversion from the subtractive primary signals for C, M, Y and K colors to the additive primary signals for R, G and B colors by analog signal processing considering these facts, has been proposed, as disclosed in Japanese Laid-Open Patent Specification No. 53-49503 (Japanese Patent Application No. 51-123795 issued May 6, 1983).
In this method, when such a signal conversion is performed, the calculations for the R, G and B color densities of the printed matters printed by the single color ink C, M, Y or K, the expected color densities of the printed matter printed by the color inks, correction values against the addition law failure, and correction values against the gamma characteristics of a color monitor can be carried out quickly by an analog method. However, when these calculations are replaced simply by a digital process which possesses the stability and the operativity, it takes a lot of time to process the operation, which is not practicable.
When the printing conditions are the same, a combination of picture signals for cyan C, magenta M, yellow Y and black K correspond unconditionally to a combination of picture signals for red R, green G and blue B. Accordingly, a conversion table for converting the combination of picture signals for C, M Y and K colors into the combination of picture signals for R, G and B colors is prepared and stored in a memory in advance, and then this table memory is utilized as occasion demands, with the result that the processing speed is largely raised.
This conversion method is very effective when the gradation of the picture signal for each C, M, Y or K color is rough, but when the gradation becomes fine, the table memory requires a large capacity.
For example, when the gradation of the signal for C, M, Y or K color is 256 steps, the table memory requires 256.sup.4 =2.sup.32 =4.times.10.sup.9 =4 giga addresses, each address storing data for 256 gradation steps of R, G or B picture signal. Thus, a large memory is necessary, which is not practicable.
Then, in order to save the capacity of the memory, a memory which stores the data of R, G and B picture signals for the combinations (16 gradation steps) of the upper four bits of C, M, Y and K picture signals, each being represented in 256 gradation steps corresponding to eight bits, is prepared, and the skipped parts are obtained by a linear interpolation method using the data of the lower four bits of C, M, Y and K picture signals, thereby obtaining R, G and B picture signals having the desired accuracy.
In this case, the table memory is provided with 16.sup.4 =2.sup.16 =65,536 addresses, each storing the four bit data for 16 gradation steps of R, G and B picture signals. In the interpolation operation, the obtained values should be continuous not only in each interpolation section but also between the adjacent interpolation sections.
In FIG. 1 there is shown an interpolation cube unit with eight vertices having coordinates (C.sub.i,M.sub.i,Y.sub.i), (C.sub.i+1,M.sub.i,Y.sub.i), (C.sub.i,M.sub.i+1,Y.sub.i), (C.sub.i,M.sub.i,Y.sub.i+1), (C.sub.i+1,M.sub.i+1,Y.sub.i), (C.sub.i+1,M.sub.i,Y.sub.i+1), (C.sub.i,M.sub.i+1,Y.sub.i+1) and (C.sub.i+1,M.sub.i+1,Y.sub.i+1), and a point P having coordinates C.sub.i +C.sub.f,M.sub.i +M.sub.f,Y.sub.i +Y.sub.f) at which the value U(C,M,Y) is to be interpolated, and wherein C.sub.i, M.sub.i and Y.sub.i representing integral parts correspond to the upper four bits of the eight bit picture signals for C, M and Y colors and C.sub.f, M.sub.f and Y.sub.f representing decimal parts correspond to the lower four bits of the same.
The cube unit is divided up into eight rectangular parallelepipeds by three planes which include the point P and are parallel to its faces. The value U(C,M,Y,) at the point P is obtained by adding up the values obtained by multiplying each known value at each of the vertices of the cube unit by the volume of each rectangular parallelepiped which is positioned opposite to that vertex, thereby obtaining the following formula (I), wherein 1&gt;C.sub.f,M.sub.f,Y.sub.f .gtoreq.0: ##EQU1##
In this interpolation method of the formula I, the obtained values are continuous not only in each interpolation section but also between the adjacent interpolation sections. Further, it is clear that the value obtained in the center of each face of the cube unit is the mean value of the known values at each vertex of that face and the value obtained at the center of the cube is the mean value of the eight known values at the vertices of the cube. Accordingly, this method is mathematically reasonable.
It seems proper that this interpolation method expressed by the formula I can be extensively applicable to interpolate the combination of R, G and B picture signal data stored in the table memory, which corresponds to the combination of C.sub.i, M.sub.i, Y.sub.i and K.sub.i which are represented by the upper four bits of the combination of the eight bit picture signals for C, M, Y and K colors, as follows. ##EQU2##
In this interpolation method expressed by the formula II, the obtained values are continuous not only in each interpolation section but also between the adjacent interpolation sections. However, this interpolation method involves 16 terms to be multiplied, and four multiplications for each term of the fifth dimension. Therefore, this method requires a complicated arithmetic circuit which has high cost, and slows the quickness of the processing operation.
Further, although, in this method, values which are smoothly continuous between the adjacent interpolation sections are obtained, the variations or the differential values of the interpolated values often become largely discontinuous. Similar disadvantages and inconveniences are found in the three-dimensional conversion according to the formula I.
In order to remove these disadvantages and inconveniences, a three-dimensional interpolation method has been proposed, as disclosed in Japanese Laid-Open Patent Specification No. 53-123201 (Japanese Patent Application No. 52-37198 issued Oct. 27, 1983). This method will be described in connection with FIGS. 2 and 3.
In FIG. 2 there is shown a dissection of a cube unit with eight vertices having coordinates (x.sub.i,y.sub.i z.sub.i), (x.sub.i+1,y.sub.i,z.sub.i), (x.sub.i,y.sub.i+1,z.sub.1), (x.sub.i,y.sub.i,z.sub.i+1), (x.sub.i+1,Y.sub.i+1,z.sub.i), (x.sub.i+1,y.sub.i,z.sub.i+1), (x.sub.i,y.sub.i+1,z.sub.i+1) and (x.sub.i+1,y.sub.i+1,z.sub.i+1), which is dissected into six tetrahedra by three planes x.sub.f =y.sub.f, y.sub.f =z.sub.f, and z.sub.f =x.sub.f which include the vertices (x.sub.i,y.sub.i,z.sub.i), (x.sub.i+1,y.sub.i+1,z.sub.i), (x.sub.i,y.sub.i,z.sub.i+1) and (x.sub.i+1,y.sub.i+1,z.sub.i+1); the vertices (x.sub.i,y.sub.i,z.sub.i), (x.sub.i+1,y.sub.i,z.sub.i), (x.sub.i+y,y.sub.i+1,z.sub.i+1) and (x.sub.i,y.sub.i+1,z.sub.i+1); and the vertices (x.sub.i y.sub.i,z.sub.i), (x.sub.i+1,y.sub.i,z.sub.i+1), (x.sub.i+1,y.sub.i+1,z.sub.i+1) and (x.sub.i,y.sub.i+1,z.sub.i), respectively.
Now, a point P to be interpolated, having the coordinates (x.sub.i +x.sub.f,y.sub.i +y.sub.f,z.sub.i +z.sub.f), lies within the tetrahedron ABCD with the coordinates (x.sub.i,y.sub.i,z.sub.i), (x.sub.i+1,y.sub.i,z.sub.i), (x.sub.i+1,y.sub.i+1,z.sub.i) and (x.sub.i+1,y.sub.i+1,z.sub.i+1) under the conditions that 1&gt;x.sub.f .gtoreq.y.sub.f .gtoreq.z.sub.f .gtoreq.0, as shown in FIG. 3.
In this case, the value U(x,y,z) at the point P is calculated as follows: draw lines from each vertex A, B, C and D through the point P to meet the opposite sides of the tetrahedron ABCD in A', B', C' and D'. The values U(x.sub.i y.sub.i,z.sub.i), U(x.sub.i+1,y.sub.i,z.sub.i), U(x.sub.i+1,y.sub.i+1,z.sub.i) and U(x.sub.i+1,y.sub.i+1,z.sub.i+1) at the vertices A, B, C and D are known. Then, the interpolated value U(P) is equal to ##EQU3##
Similar discriminating conditions and calculating factors can be worked out for the other five tetrahedra. Table 1 shows a complete set of the discrimination conditions and calculating factors for the interpolations. It is readily appreciated that this calculation method is easier than the method of formula I, although at a slight loss in accuracy. Further, in this method, there is no danger that the interpolated values may be discontinuous not only in each interpolation section but also between the adjacent interpolation sections.
In Formula III, the weighting factors for the known values of the vertices A, B, C and D of the tetrahedron ABCD are shown by the ratios of the edges of the tetrahedron ABCD shown in FIG. 3 when the linear interpolation is carried out by using the known values of the vertices A, B, C and D. However, since the ratios ##EQU4## correspond to the ratios ##EQU5## of the volumes of the tetrahedra, respectively, the ratios of the edges of the tetrahedron can be replaced with the ratios of the volumes of the tetrahedra.